package algorithm.calculator;

import java.util.ArrayDeque;
import java.util.Deque;

/*计算器*/
public class Template {
    /*给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。
    表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格  。 整数除法仅保留整数部分。
    示例："3+2*2"，输出7，输入" 3+5 / 2 "，输出5*/
    /*
     * 在 Java 中，Deque（双端队列）接口继承自Queue接口，具有以下一些主要特性：
     * 1. 双端操作
     * 可以在队列的两端进行插入和删除操作
     * - 在队首进行插入和删除：可以使用addFirst、offerFirst、removeFirst、pollFirst、peekFirst等方法在双端队列的头部进行操作
     * - 在队尾进行插入和删除：可以使用addLast、offerLast、removeLast、pollLast、peekLast等方法在双端队列的尾部进行操作
     * 2. 队列操作
     * 作为队列使用
     * - 可以像普通队列一样，在队尾插入元素（使用add/offer），从队首移除元素（使用remove/poll）和查看队首元素（使用peek）。
     * 3. 栈操作
     * 作为栈使用：
     * - 可以把双端队列当成栈来使用，在一端进行入栈（使用push，相当于addFirst）和出栈(使用pop，相当于removeFirst)操作
     */
    public static int calculate(String s) {
        int n = s.length();
        Deque<Integer> stack = new ArrayDeque<>();
        int num = 0;
        char sign = '+';
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                /*整体上，这个表达式就是不断地将新读取的数字字符整合到正在构建的整数值中。每次读取一个数字字符，都通过这个表达式更新 num 的值，直到处理完整个数字字符串。*/
                num = num * 10 + (c - '0');
            }
            // Character.isDigit(c)：判断是否为数字，Character.isWhitespace(c)判断是否为空格
            if ((!Character.isDigit(c) && !Character.isWhitespace(c)) || i == n - 1) {
                // 这里的sign实际就是上一次的sign值，所以stack push时，取决于上一次的sign值
                if (sign == '-') {
                    stack.push(-num);
                } else if (sign == '+') {
                    stack.push(num);
                } else if (sign == '*') {
                    stack.push(stack.pop() * num);
                } else if (sign == '/') {
                    stack.push(stack.pop() / num);
                }
                sign = c; // 记录上一次的符号，为后续的sign判断做准备
                num = 0;
            }
        }
        int res = 0;
        while (!stack.isEmpty()) {
            res += stack.pop();
        }
        return res;
    }

    public static void main(String[] args) {
//        String s = " 3+5 / 2 ";
//        int res = calculate(s);
        String s = "(1+(4+5+2)-3)+(6+8)";
        calculate1(s);

    }
    /*基础计算器实现：包含了(1+(4+5+2)-3)+(6+8)，s 由数字、'+'、'-'、'('、')'、和 ' ' 组成*/
    public static int calculate1(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        int sign = 1; // 这里的1表示正数，-1表示负数
        int result = 0; // 返回的结果
        int num = 0; // 连续多次完整的数字组合
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            // + - 都是实时计算的
            if (Character.isDigit(c)){
                num = num * 10 + (c - '0');
            } else if (c == '+') {
                result += sign * num;
                num = 0;
                sign = 1;
            } else if (c == '-') {
                result += sign * num;
                num = 0;
                sign = -1;
            }else if (c == '('){
                stack.push(result);
                stack.push(sign);
                result = 0;
                sign = 1;
            }else if (c == ')'){
                // 因为都是实时计算，所以即使在括号中也就存放两个值
                result += sign * num; // 实时计算的，先将当前的数字num和当前符号相乘，并累加到结果result中
                num = 0;
                // 从栈中弹出上一个符号和上一个结果
                int prevSign = stack.pop(); // 因为存放的顺序是优先存在result，然后存放符号，所以优先取符号
                int prevResult = stack.pop();
                result = prevResult + prevSign * result;
            }

        }
        return result + sign * num;
    }
}
